package HashMap;

import java.util.HashMap;

/**
 *  题目：最近最少使用缓存
 *  题目详述 ：
 *  运用所掌握的数据结构，设计和实现一个 LRU (Least Recently Used，最近最少使用) 缓存机制 。
 * 实现 LRUCache 类：
 * LRUCache(int capacity) 以正整数作为容量capacity 初始化 LRU 缓存
 * int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
 * void put(int key, int value)如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。
 * 当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
 *
 */
public class OfferP31 {
    /**
     * 思路 ：哈希表(key = “key”，value = “双向链表的节点”) + 双向链表(用于存储真实数据)
     * 思考 ：若是仅仅使用哈希表的话，不能够实现当缓存容量到达上限时，在写入新数据之前，先删除最久未使用的数据；
     */
    public final int FALSE_NUMBER = -1;
    private ListNode head;
    private ListNode tail;
    HashMap<Integer, ListNode> map;
    // 通过hashmap，来实现获取查询节点的时间复杂度为O（1）
    private int cap;
    // 定义类局部变量cap（缓存容器大小），为方便后续使用
    public OfferP31(int capacity) {
        // 定义两个哨兵节点，分别指向双向链表的头部和尾部
        // （作用在于，当缓存容器已经满了时，需要新插入双向链表结点时，需要删除head哨兵节点所指向的节点，同时在tail哨兵节点处，插入新节点）
        head = new ListNode(-1 , -1);
        tail = new ListNode(-1 , -1);
        map = new HashMap<>();
        /**
         * 在双向链表没有任何元素的情况下 ：
         *  tail.prev在双向链表在尾部节点插入时，需要知道tail节点的prev节点；
         *  head.next在双向链表在缓存容器已满和需要插入一个新的节点的条件下，需要知道head节点的next节点
         */
        tail.prev = head;
        head.next = tail;
        cap = capacity;
    }
    // 若是map中包含key值的话，即通过map中的value（ListNode节点），获取到真实数据
    public int get(int key) {
        if(map.containsKey(key)){
            // 在查询缓存容器中记录时，若是记录存在时，需要将其插入到双向链表的尾部（代表其为最新被访问的）
            ListNode node = map.get(key);
            deleteNode(node);
            insertNodeTail(node);
            return node.value;
        }
        return FALSE_NUMBER;
    }

    /**
     * 思路 ：
     * （1）若是缓存容器中存在此key的话，需要将此存在的节点放置到双向链表的尾部(由于没有新的节点插入，所以不需要去考虑缓存容器到达上限)
     *  (2) 若是缓存容器中不存在此key的话，需要判断缓存容器中是否已经满了
     *  ===》容器满了的前提下，即需要去删除双向链表的第一个节点（其所指向的是最久未使用的节点）
     *  (3)同时，当插入节点的情况下，需要向双向链表的尾部节点进行节点的插入
     * @param key
     * @param value
     */
    public void put(int key, int value) {
        if(map.containsKey(key)){
            moveToTail(map.get(key),value);
        }
        else {
            if(map.size() == cap){
                ListNode node = head.next;
                deleteNode(node);
                // 同时，记住需要在hashmap中将缓存容器中所存储的节点删除
                map.remove(node.key);
            }
            // 由于缓存容器中不存在此节点，即需要在尾部新增一个节点（在新建节点的情况下）
            ListNode node = new ListNode(key, value);
            insertNodeTail(node);
            map.put(key,node);
        }
    }
    // 在缓存容器包含此key时，将此键值对的value进行覆盖，同时将其插入双向链表的尾部（代表其为最新的）
    private void moveToTail(ListNode node,int value) {
        deleteNode(node);

        node.value = value;

        insertNodeTail(node);
    }
    // 双向链表中删除某个节点
    // 由于是双向链表，若是需要去删除一个节点的话，则前后节点的指针都需要进行变换
    public void deleteNode(ListNode node){
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    // 节点插入到双向链表的尾部（通过tail节点 ===> 双向链表的尾部哨兵节点）
    public void insertNodeTail(ListNode node){
        // 在双向链表的尾部插入节点
        tail.prev.next = node;
        node.prev = tail.prev;
        node.next = tail;
        tail.prev = node;
    }

    // 双向链表的定义(存储了缓存容量的真实数据)
    class ListNode{
        private int key;
        private int value;
        private ListNode prev;
        private ListNode next;

        public ListNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
}
